package com.example.find;

/**
 * @author zhy
 * @version 1.0.0
 * @ClassName FindSolution3.java
 * @Description 找到第k个最小元素
 * @createTime 2020年12月22日 17:10:00
 */
public class FindSolution3 {

    public static void quickSelect(int[] nums, int left, int right, int k) {
        if (right - left <= 1) {
            return;
        }
        int pivot = findPivot(nums, left, right);
        int i = left;
        int j = right - 1;
        for (;;) {
            while (nums[++i] < pivot) {}
            while (nums[--j] > pivot) {}
            if (i < j) {
                swap(nums, i, j);
            } else {
                break;
            }
        }
        swap(nums, i, right - 1);
        if (i == k) {
            return;
        } else if (i > k) {
            quickSelect(nums, left, i - 1, k);
        } else {
            quickSelect(nums, i + 1, right, k - i + 1);
        }
    }

    //  寻找支点的方法，将两个端点和中间位置的三个元素的中间元素值作为支点
    //  顺便让left小于支点元素小于right，可以减少一次比较次数
    public static int findPivot(int[] nums, int left, int right) {
        int mid = (left + right) / 2;
        if (nums[left] > nums[mid]) {
            swap(nums, left, mid);
        }
        if (nums[right] < nums[mid]) {
            swap(nums, right, mid);
        }
        if (nums[left] > nums[right]) {
            swap(nums, left, right);
        }
        //将支点元素移动到最右边元素的左边，这样可以减少一次比较次数
        swap(nums, mid, right - 1);
        return nums[right - 1];
    }

    public static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static void main(String[] args) {
        int[] a = {90, 90, 67, 3, 3, 8, 43, 89, 90, 90};
        System.out.print("原数组为：");
        int k = 4;
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + ",");
        }
        System.out.println();
        quickSelect(a, 0, a.length - 1, k);
        System.out.println();
        System.out.println("第"+k+"小的元素为");
        System.out.println(a[k - 1]);

    }
}
